//Accepted
#include <cstdio>
#include <cstring>

int A[300000], B[300000], array[50200];

void initialize_A(int node, int start,int end){
	if (start==end)
		A[node] = start;
	else
	{
		int mid = (start+end)/2;
		initialize_A(2*node,start,mid);
		initialize_A(2*node+1,mid+1,end);
		if (array[A[2*node]]<=
			array[A[2*node+1]])
			A[node] = A[2 * node];
		else
			A[node] = A[2 * node + 1];
		
	}
}
int query_A(int node, int start,int end, int i, int j){
	int id1,id2;
	if (i>end || j<start)
		return -1;
	if (start>=i && end<=j)
		return A[node];
	
	int mid = (start+end)/2;
	id1 = query_A(2*node,start,mid,i,j);
	id2 = query_A(2*node+1,mid+1,end,i,j);
	
	if (id1==-1)
		return id2;
	if (id2==-1)
		return id1;
	
	if (array[id1]<=array[id2])
		return id1;
	else
		return id2;
}


void initialize_B(int node, int start,int end){
	if (start==end)
		B[node] = start;
	else
	{
		int mid = (start+end)/2;
		initialize_B(2*node,start,mid);
		initialize_B(2*node+1,mid+1,end);
		if (array[B[2*node]]>=
			array[B[2*node+1]])
			B[node] = B[2 * node];
		else
			B[node] = B[2 * node + 1];
		
	}
}
int query_B(int node, int start,int end, int i, int j){
	int id1,id2;
	if (i>end || j<start)
		return -1;
	if (start>=i && end<=j)
		return B[node];
	
	int mid = (start+end)/2;
	id1 = query_B(2*node,start,mid,i,j);
	id2 = query_B(2*node+1,mid+1,end,i,j);
	
	if (id1==-1)
		return id2;
	if (id2==-1)
		return id1;
	
	if (array[id1]>=array[id2])
		return id1;
	else
		return id2;
}

int main()
{
	//freopen("in.txt", "r", stdin);
    int i,j,N, Q;
	memset(A,-1,sizeof(A));
	memset(B,-1,sizeof(B));
	
    scanf("%d%d",&N, &Q);
    for (i=0;i<N;i++)
        scanf("%d",&array[i]);

    initialize_A(1,0,N-1);
	initialize_B(1,0,N-1);
	
    while (scanf("%d%d",&i,&j)==2)
      printf("%d\n",array[query_B(1,0,N-1,i-1,j-1)] - array[query_A(1,0,N-1,i-1,j-1)]);
}
